#include <iostream>
#include "test_utilities.hpp"
#include "../tree.hpp"
#include "tree_test.hpp"

using std::cout;
using std::endl;

namespace treeTest {

void testCreate();
void testInsert();
void testRemove();
void testMinFrom();

void run_tree_tests() {
	RUN_TEST(testCreate);
	RUN_TEST(testInsert);
	RUN_TEST(testRemove);
	RUN_TEST(testMinFrom);
}

class IntID {
	int id;
public:
	bool operator<(const IntID& otherId) const {
		return id < otherId.getId();
	}
	bool operator==(const IntID& otherId) const {
		return id == otherId.getId();
	}
	bool operator!=(const IntID& otherId) const {
		return !(*this == otherId);
	}
	IntID(int id) : id(id) {};
	int getId() const {
		return id;
	}
};

void testCreate() {
	ASSERT_NO_THROW(AvlTree<IntID>());
}

void testInsert() {
	AvlTree<IntID> tree;
	const int interval = 3;
	const int valuesAmount = 100;
	for (int firstValue = 0; firstValue < interval; ++firstValue) {
		for (int i = firstValue; i < valuesAmount; i += interval) {
			ASSERT_NO_THROW(tree.insert(IntID(i)));
		}
	}

	ASSERT_TRUE(valuesAmount == tree.getSize());

	for (int firstValue = 0; firstValue < interval; ++firstValue) {
		for (int i = firstValue; i < 100; i += interval) {
			ASSERT_TRUE(NULL != tree.find(IntID(i)));
		}
	}
}

void testRemove() {
	AvlTree<IntID> tree;
	const int interval = 3;
	const int valuesAmount = 100;

	// Remove in sequential order
	for (int firstValue = 0; firstValue < interval; ++firstValue) {
		for (int i = firstValue; i < valuesAmount; i += interval) {
			ASSERT_NO_THROW(tree.insert(IntID(i)));
		}
	}
	for (int i = 0; i < valuesAmount; ++i) {
		ASSERT_NO_THROW(tree.remove(IntID(i)));
		ASSERT_THROWS(NoSuchElementException, tree.remove(IntID(i)));
		ASSERT_EQUALS(valuesAmount - 1 - i, tree.getSize());
	}

	// Remove not in sequential order
	for (int firstValue = interval - 1; firstValue >= 0; --firstValue) {
		for (int i = firstValue; i < valuesAmount; i += interval) {
			ASSERT_NO_THROW(tree.insert(IntID(i)));
		}
	}
	int nodesLeftAmount = valuesAmount;
	for (int firstValue = 0; firstValue < interval; ++firstValue) {
		for (int i = firstValue; i < valuesAmount; i += interval) {
			ASSERT_NO_THROW(tree.remove(IntID(i)));
			ASSERT_THROWS(NoSuchElementException, tree.remove(IntID(i)));
			--nodesLeftAmount;
			ASSERT_EQUALS(nodesLeftAmount, tree.getSize());
		}
	}
}

void testMinFrom() {
	AvlTree<IntID> tree;
	const int interval = 3;
	const int valuesAmount = 100;
	ASSERT_THROWS(NoSuchElementException, tree.findMinFrom(IntID(3)));

	for (int firstValue = 0; firstValue < interval; ++firstValue) {
		for (int i = firstValue; i < valuesAmount; i += interval) {
			tree.insert(i);
			ASSERT_EQUALS(i, tree.findMinFrom(IntID(i)));
			ASSERT_THROWS(NoSuchElementException, 
				tree.findMinFrom(IntID(valuesAmount)));
			if ((firstValue > 0) && (i < valuesAmount - interval)) {
				ASSERT_EQUALS(i + 3 - firstValue, 
					tree.findMinFrom(IntID(i + 1)));
			}
		}
	}
}

}
